class Graph(object):
    
    def __init__(self):
        self.num_edges = 0
        self.vertices = set()
        self.adjacency_list = {}
        
    def v(self):
        return len(self.vertices)
    
    def v(self):
        return self.num_edges

    def adj(self, v):
        if not v in self.vertices:
            return []
        return self.adjacency_list[v]

    def add_edge(self, v, w):
        if not v in self.vertices:
            self.add_vertex(v)
        if not w in self.vertices:
            self.add_vertex(w)
        if w not in self.adjacency_list[v]:
            self.adjacency_list[v].append(w)
        if v not in self.adjacency_list[w]:
            self.adjacency_list[w].append(v)
        self.num_edges += 1

    def add_vertex(self, v):
        if v in self.vertices:
            return
        self.vertices.add(v)
        self.adjacency_list[v] = []

    def degree(self, v):
        adjs = self.adj(v)
        return len(adjs)

    def max_degree(self):
        max_degree = 0
        for v in self.vertices:
            degree = self.degree(v)
            if degree > max_degree:
                max_degree = degree
        return max_degree

    def __str__(self):
        s = f"{len(self.vertices)} vertices\n"
        for v in self.vertices:
            s += f"{v.id} : "
            for d in self.adj(v):
                s += f"{d.id} "
            s += "\n"
        return s
    